import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Random;
import java.util.StringTokenizer;


public class RSAMain {

	/**
	 * @param args
	 */
	static BigInteger p , q, n, phi,e , d;
	static BigInteger ZERO = BigInteger.ZERO;
	static BigInteger ONE = BigInteger.ONE;
	static BigInteger TWO = new BigInteger ("2");
	static BigInteger THREE = new BigInteger ("3");
	static int num_bits = 128;
	
	public static BigInteger randomBigInteger(){
		Random random = new Random();
		BigInteger x = new BigInteger(num_bits/2, random);
		
		if ((x.remainder(TWO)).equals(ZERO))
			x = x.add(BigInteger.ONE);
		
		return x;
	}
	
	public static BigInteger modPow(BigInteger b, BigInteger e, BigInteger m){
//		System.out.println("  modpow: "+b+" "+e+" "+m);
		String exp = e.toString(2);
		BigInteger results = ONE;
		int pos = exp.length()-1;
		while(pos > -1){
			if(exp.charAt(pos) == '1')
				results = results.multiply(b).mod(m);
				
			b = b.multiply(b);
			b = b.mod(m);
			
			pos--;
		}
//		System.out.println("modpow: "+ results);
		return results;
	}
	public static boolean checkPrime(BigInteger prime){
		int i = 0;
		boolean flag = true;
		BigInteger old = prime.subtract(BigInteger.ONE);
		//tim old vs i; 2^i*old = prime
		while(flag){
			if(old.mod(TWO).equals(BigInteger.ZERO)){
				old = old.divide(TWO);
				i++;
			}
			else
				flag = false;
		}
		return check(prime, i, old, 0);
	}
	
	/**
	 * 
	 * @param prime
	 * @param i
	 * @param old
	 * @param n
	 * @return true	: neu no co the la so prime
	 * 		   false: neu no hong phai la so prime
	 * dung giai thuat Miller-Rabin voi 10 lan lap se cho ta sai so la 0.00009%
	 */	 
		public static BigInteger randomInt(){
			Random random = new Random();
			BigInteger results = new BigInteger(20, random);
			return results;
		}
	public static boolean check(BigInteger prime, int i, BigInteger old, int n){
		if(n >= 11)return true;
		BigInteger a;
		while(true){
			a = randomInt().add(BigInteger.ONE);
			if(a.compareTo(prime.subtract(BigInteger.ONE)) == -1 && a.compareTo(BigInteger.ONE) == 1)break;
		}
		//kiem tra a^old% prime co bang 1 khong
		if(modPow(a, old,  prime).equals(BigInteger.ONE) ){
			n++;
			return check(prime, i, old, n);
		}
		if(modPow(a, old,  prime).equals(prime.subtract(BigInteger.ONE))){//kiem tra a^(2^j*old) % prime co bang prime-1 khong
			n++;
			return check(prime, i, old, n+1);
		}
		int k = 1;
		for(int j = 1; j < i; j++){
			k = k*2;
			BigInteger mu = new BigInteger(Integer.toString(k, 10));
			if(modPow(a, old.multiply(mu),  prime).equals(prime.subtract(BigInteger.ONE))){//kiem tra a^(2^j*old) % prime co bang prime-1 khong
				n++;
				return check(prime, i, old, n+1);
			}
		}
		return false;
	}
	



	/*
	public static boolean checkPrime(BigInteger prime){
		boolean flag = true;
		int k = 0;
		BigInteger old = prime.subtract(ONE);
		while(old.mod(TWO).equals(ZERO)){
			old = old.divide(TWO);
			k++;
		}
//		System.out.println(prime+" "+k+" "+old);
		
		int rd = 2;
		for(int i = 0; i< 10 ; i++){
			if(flag == false)
				break;
			BigInteger a = new BigInteger(Integer.toString(rd));//System.out.println(a.toString());
			while(!(prime.subtract(ONE).compareTo(a) == 1)){
				rd++;
				a = new BigInteger(Integer.toString(rd));
			}
//			System.out.println(a.toString());
			//System.out.print("  ");
			BigInteger result = modPow(a, old, prime);
			if(result.equals(ONE)||result.equals(prime.subtract(ONE))){
				rd++;
				continue;
			}
			else{
				int j;
				for(j = 1; j < k; j++){
//					System.out.println("j "+j);
					result = modPow(result, TWO, prime);
					
					if(result.equals(ONE))
						return false;
					if(result.equals(prime.subtract(ONE)))
						break;
				}
				if(j < k){
					rd++;
					continue;
				}
				return false;
			}
			
		}
		return true;
	}*/
	
	public static BigInteger GCD(BigInteger a, BigInteger b){
		if(a.mod(b) == BigInteger.ZERO) return b;
		else return GCD(b, a.mod(b));
	}
	
	public static BigInteger findInverse(){

		BigInteger[] arr = new BigInteger[7];
		arr[0] = phi;
		arr[1] = e;
		arr[2] = arr[0].mod(arr[1]);
		arr[3] = arr[0].divide(arr[1]);
		arr[4] = ZERO;
		arr[5] = ONE;
		arr[6] = arr[4].subtract(arr[3].multiply(arr[5]));
		//System.out.println(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]+" "+arr[4]+" "+arr[5]+" "+arr[6]);
		while(true){
			arr[0] = arr[1];
			arr[1] = arr[2];
			arr[2] = arr[0].mod(arr[1]);
			if(arr[2].equals(ZERO))
				return arr[6].compareTo(ZERO)==-1?phi.add(arr[6]):arr[6];
			arr[3] = arr[0].divide(arr[1]);
			arr[4] = arr[5];
			arr[5] = arr[6];
			arr[6] = arr[4].subtract(arr[3].multiply(arr[5]));//System.out.println(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]+" "+arr[4]+" "+arr[5]+" "+arr[6]);
		}
		
	}
	
	public static void createKey(){
		
		p = randomBigInteger();//BigInteger.probablePrime(50, new Random());
		while(!checkPrime(p))
			p = p.add(TWO);
		
		q = randomBigInteger();//BigInteger.probablePrime(50, new Random());
		while(!checkPrime(q))
			q = q.add(TWO);
		
		n = p.multiply(q);
//		System.out.println("n : \n"+n);
		phi = p.subtract(ONE).multiply(q.subtract(ONE));
		
		e = new BigInteger("65537");
		if(!GCD(phi, e).equals(ONE)){
			e = new BigInteger("17");
			if(!GCD(phi, e).equals(ONE)){
				e = new BigInteger("65537");
				if(!GCD(phi, e).equals(ONE))
					System.out.println("Cannot select e");
			}
		}
//		System.out.println("e\n"+e.toString());
		d = findInverse();
//		System.out.println("d\n"+d.toString());
	
//		System.out.println("p\n"+p+"\nq\n"+q);
	}
	
	public static void encrypt(String fileIn, String fileOut, BigInteger n, BigInteger ed) throws IOException{
		FileInputStream fis = new FileInputStream(fileIn);
		DataOutputStream fos = new DataOutputStream(new FileOutputStream(fileOut));

		int len = 0;
		byte[] inText = new byte[3]; 
		
		int i =0;
		while ((len = fis.read(inText)) > 0)
		{
			System.out.println(i++);
			//System.out.println("inText "+new String(inText));
			
			BigInteger message = new BigInteger(inText);
			System.out.println("message "+message.toString());
			
			BigInteger cipher = modPow(message, e, n);
			System.out.println("cipher "+cipher.toString());
			
			String pad = cipher.toString(2);
			String pad2 = String.format("%128s", pad).replace(' ', '0');
			
			//System.out.println("pad  "+pad);
			//System.out.println("pad2 "+pad2);
			
			String t ="", kq="";
			for(int k=0; k<pad2.length(); k++){
				if(k%8==7){
					t=t+pad2.charAt(k);
					System.out.println(t);
					int num = Integer.valueOf(t, 2);
					//num =99;
					kq += new Character((char)num).toString();
					System.out.println(num+" "+kq);
					t = "";
				}
				else
					t=t+pad2.charAt(k);
			}

			//System.out.print(kq);
			fos.writeChars(kq);
	
//			byte[] outText = plain.toByteArray();
//			fos.write(outText);
//			System.out.println("outText "+new String(outText));
			
			
		}

		fis.close(); 
		fos.close();
	}
	
	public static void decrypt(String fileIn, String fileOut, BigInteger n, BigInteger ed) throws IOException{
		DataInputStream fis = new DataInputStream(new FileInputStream(fileIn));	
		FileOutputStream fos = new FileOutputStream(fileOut);
		
//		InputStreamReader isr = new InputStreamReader(fis);
//		OutputStreamWriter osr = new OutputStreamWriter(fos);
//		
//		BufferedReader in = new BufferedReader(isr);

		int len = 0;
		byte[] inText = new byte[1]; 
		
		int i =0;
		while ((len = fis.read(inText)) > 0)
		{
			System.out.println(i++);
			//System.out.println("inText "+new String(inText));
			
			BigInteger cipher = new BigInteger(inText);
			System.out.println("cipher "+cipher.toString());
			
			BigInteger plain = modPow(cipher, d, n);
			System.out.println("plain "+plain.toString());
			
	
			byte[] outText = plain.toByteArray();
			fos.write(outText);
			System.out.println("outText "+new String(outText));
			
			
		}

		fis.close(); 
		fos.close();
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		createKey();
		encrypt("input.txt", "output.txt", n, e);
		decrypt("output.txt", "reinput.txt", n, d);
	}
	
	

}
